package com.ww.algorithm.question.list.reverse;

public class ListReverseRecursive {

    public static LNode<Integer> recursiveReverse(LNode<Integer> head) {
        if (null == head || null == head.getNext()) {
            return head;
        } else {
            // 反转后面结点
            LNode<Integer> newHead = recursiveReverse(head.getNext());
            // 把当前遍历的结点加到后面结点逆序后链表的尾部
            head.getNext().setNext(head);
            head.setNext(null);
            return newHead;
        }
    }

    public static void reverse(LNode<Integer> head) {
        if (null == head) {
            return;
        }

        LNode<Integer> firstNode = head.getNext();
        // 对链表进行逆序
        LNode<Integer> newHead = recursiveReverse(firstNode);
        head.setNext(newHead);
    }

    public static void main(String[] args) {
        LNode<Integer> head = new LNode<>();
        head.setNext(null);
        LNode<Integer> tmp = null;
        LNode<Integer> cur = head;
        for (int i = 0; i < 8; i++) {
            tmp = new LNode<>();
            tmp.setData(i);
            tmp.setNext(null);
            cur.setNext(tmp);
            cur = tmp;
        }
        System.out.println("逆序前：");
        for (cur = head.getNext(); cur != null; cur = cur.getNext()) {
            System.out.print(cur.getData() + " ");
        }
        System.out.println("\n逆序后");
        reverse(head);
        for (cur = head.getNext(); cur != null; cur = cur.getNext()) {
            System.out.print(cur.getData() + " ");
        }
    }
}
